package com.leetcode.根据数据结构分类.二叉树;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * @author: ZhouBert
 * @date: 2021/3/19
 * @description: 剑指 Offer 33. 二叉搜索树的后序遍历序列
 * https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/
 */
public class B_剑指Offer33_二叉搜索树的后序遍历序列 {
	public static void main(String[] args) {
		test4();
//		test1();
//		test2();
//		test3();
	}

	public static void test1() {
		//false
		B_剑指Offer33_二叉搜索树的后序遍历序列 action = new B_剑指Offer33_二叉搜索树的后序遍历序列();
		int[] postOrder = new int[]{1, 6, 3, 2, 5};
		boolean res = action.verifyPostorder(postOrder);
		System.out.println("res = " + res);
	}

	public static void test2() {
		//true
		B_剑指Offer33_二叉搜索树的后序遍历序列 action = new B_剑指Offer33_二叉搜索树的后序遍历序列();
		int[] postOrder = new int[]{1, 3, 2, 6, 5};
		boolean res = action.verifyPostorder(postOrder);
		System.out.println("res = " + res);
	}

	public static void test3() {
		//true
		B_剑指Offer33_二叉搜索树的后序遍历序列 action = new B_剑指Offer33_二叉搜索树的后序遍历序列();
		int[] postOrder = new int[]{4, 6, 7, 5};
		boolean res = action.verifyPostorder(postOrder);
		System.out.println("res = " + res);
	}

	public static void test4() {
		//true
		B_剑指Offer33_二叉搜索树的后序遍历序列 action = new B_剑指Offer33_二叉搜索树的后序遍历序列();
		int[] postOrder = new int[]{1, 6, 3, 2, 5};
		boolean res = action.verifyPostorderByStack(postOrder);
		System.out.println("res = " + res);
	}




	int[] pOrder;
	int[] iOrder;

	/**
	 * 我的思路：
	 * 缕清现有条件：
	 * 1.二叉搜索树 + 各个数字各不相同（减少需要考虑的因素）：可以得到中序遍历；
	 * 那么题目就变成，根据中序遍历判断后序遍历是否正确。
	 * 递归求解
	 *
	 * @param postorder
	 * @return
	 */
	public boolean verifyPostorder(int[] postorder) {
		int len = postorder.length;
		if (len < 2) {
			return true;
		}
		iOrder = new int[len];
		pOrder = postorder;
		System.arraycopy(pOrder, 0, iOrder, 0, len);
		Arrays.sort(iOrder);
		return check(0, len, 0, len);
		//使用递归自底向上进行判断，一旦一个环节返回false ,最终结果也返回 false
	}


	private boolean check(int poBegin, int poEnd, int ioBegin, int ioEnd) {
		//base case 还需要处理相等的情况
		if (poBegin == poEnd - 1) {
			//如果只有一个位置
			if (pOrder[poBegin] == iOrder[ioBegin]) {
				return true;
			} else {
				return false;
			}
		}
		int rootValue = pOrder[poEnd - 1];
		//1.在 inorder 中寻找 root
		int i = ioBegin;
		for (; i < ioEnd; i++) {
			if (iOrder[i] == rootValue) {
				//找到根节点
				break;
			}
		}
		//如果没有找到，进行返回结果
		if (i == ioEnd) {
			return false;
		}
		int newPoEnd = i - ioBegin + poBegin;
		if (i == ioBegin) {
			//如果没有左子节点
			return check(newPoEnd, poEnd - 1, i + 1, ioEnd);
		} else if (i == ioEnd - 1) {
			//如果没有左子节点
			return check(poBegin, newPoEnd, ioBegin, i);
		}

		return check(poBegin, newPoEnd, ioBegin, i) &&
				check(newPoEnd, poEnd - 1, i + 1, ioEnd);
	}


	/**
	 * 没想到可以用单调栈来实现，真的很了不起了
	 * 翻转后序遍历 = 前序遍历的错位，还可以跟单调栈进行关联
	 * 单调栈记录的是递增的序列，也就是二叉树往右走的序列！
	 * 由于具有【双向性】，接下来的数字要么比根节点大，要么比根节点小，所以可以考虑使用单调栈！
	 * https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/solution/dan-diao-di-zeng-zhan-by-shi-huo-de-xia-tian/
	 * @param postorder
	 * @return
	 */
	public boolean verifyPostorderByStack(int[] postorder) {
		// 单调栈使用，单调递增的单调栈
		Deque<Integer> stack = new LinkedList<>();
		// 【表示上一个根节点的元素】，这里可以把postorder的最后一个元素root看成无穷大节点的左孩子
		// 由于反转之后：root-right-left;如果已经确定了往 left 走以后，如果出现元素大于 pervElem 就说明反常！
		int pervElem = Integer.MAX_VALUE;
		// 逆向遍历，就是翻转的先序遍历
		for (int i = postorder.length - 1;i>=0;i--){
			// 左子树元素必须要小于递增栈被peek访问的元素，否则就不是二叉搜索树
			if (postorder[i] > pervElem){
				return false;
			}
			while (!stack.isEmpty() && postorder[i] < stack.peek()){
				// 数组元素小于单调栈的元素了，表示往左子树走了，记录下上个根节点
				// 找到这个左子树对应的根节点，之前右子树全部弹出，不再记录，因为不可能在往根节点的右子树走了
				pervElem = stack.pop();
			}
			// 这个新元素入栈
			stack.push(postorder[i]);
		}
		return true;
	}
}
